package leetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

public class LeetCode_day14 {

	/**
	 * Given an array with n objects colored red, white or blue, 
	 * sort them so that objects of the same color are adjacent, 
	 * with the colors in the order red, white and blue.
	 * Here, we will use the integers 0, 1, and 2 
	 * to represent the color red, white, and blue respectively.
	 * 
	 * Follow up:
	 * A rather straight forward solution is a two-pass algorithm using counting sort.
	 * First, iterate the array counting number of 0's, 1's, and 2's, 
	 * then overwrite array with total number of 0's, then 1's and followed by 2's.
	 * Could you come up with an one-pass algorithm using only constant space?
	 * @param colors
	 */
	public static void sortColors(Color[] colors){
		if(colors == null) return;
		
		System.out.println("Original: ");
		for(int i = 0 ; i < colors.length ; i++)
			System.out.print(colors[i].getName()+", ");
		/*
		 * ind1: the indicator for the end of red
		 * ind2: the indicator for the start of blue
		 * ind: the indicator for looping
		 */
		int ind1 = 0, ind2 = colors.length - 1, ind = 0;
		while(ind < ind2){
			Color temp = colors[ind];
			if(colors[ind] == Color.RED){
				colors[ind] = colors[ind1];
				colors[ind1] = temp;
				ind1++;
			}else if(colors[ind] == Color.BLUE){
				colors[ind] = colors[ind2];
				colors[ind2] = temp;
				ind2--;
				ind--;//because you don't know what color has be exchanged. We need to re-check.
			}
			ind++;
		}
		
		System.out.println();
		System.out.println("Sorted: ");
		for(int i = 0 ; i < colors.length ; i++)
			System.out.print(colors[i].getName()+", ");

		System.out.println();
	}
	
	/**
	 * Given a string S and a string T, find the minimum window in S 
	 * which will contain all the characters in T in complexity O(n).
	 * For example,
	 * S = "ADOBECODEBANC"
	 * T = "ABC"
	 * Minimum window is "BANC".
	 * Note:
	 * If there is no such window in S that covers all characters in T, return the empty string "".
	 * If there are multiple such windows, 
	 * you are guaranteed that there will always be only one unique minimum window in S.
	 * @param s
	 * @param t
	 */
	public static void minimumWindowSubstring(String s, String t){
		if(s == null || t == null || s.isEmpty() || t.isEmpty()) return;
		HashMap<Character, Integer> map = new HashMap<Character ,Integer>();
		int windowLength = Integer.MAX_VALUE;
		int windowStart = -1;
		int start = -1;
	
		//initialization
		for(Character c : t.toCharArray())
			if(map.containsKey(c)){
				int n = map.get(c);
				map.put(c, n+1);
			}else map.put(c, 1);
		
		char[] cs = s.toCharArray();
		for(int i = 0 ; i < cs.length ; i++){
			if(!map.containsKey(cs[i])) continue;
			if(windowStart == -1) windowStart = i;
			int num = map.get(cs[i]);
			map.put(cs[i], num-1);
			boolean flag = true;
			for(Character k : map.keySet())
				if(map.get(k) > 0){
					flag = false;
					break;
				}
			if(flag){//find window
				int len = i - windowStart + 1;
				if(len < windowLength){
					windowLength = len;
					start = windowStart;
				}
				//start a new search for another window
				for(int j = windowStart + 1; j <= i ; j++){
					if(map.containsKey(cs[j])){
						windowStart = j;
						num = map.get(cs[j]);
						map.put(cs[j], num--);
						break;
					}
				}
			}
		}
		
		if(windowLength == Integer.MAX_VALUE) return;
		System.out.println();
		System.out.println("Window: ");
		for(int i = start ; i < start + windowLength ; i++)
			System.out.print(cs[i]);
		System.out.println();
	}
	
	/**
	 * Given two integers n and k, 
	 * return all possible combinations of k numbers out of 1 ... n.
	 * For example,
	 * If n = 4 and k = 2, a solution is:
	 * [
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
		]
	 * @param n
	 * @param k
	 */
	public static void combinations(int n, int k){
		if(k > n) return;
		if(n < 1) return;
		
		List<int[]> res = new ArrayList<int[]>();
		combi(1, n, 0, k-1, new int[k], res);
		
		System.out.println();
		for(int[] re : res){
			for(int i : re)
				System.out.print(i+", ");
			System.out.println();
		}
		System.out.println();
	}
	
	private static void combi(int start, int n, int th, int k, int[] path, List<int[]> res){
		if(th > k){
			res.add(path);
			return;
		}
		
		for(int i = start ; i <= n-k+th ; i++){
			int[] newPath = Arrays.copyOf(path, path.length);
			newPath[th] = i;
			combi(i+1, n, th+1, k, newPath, res);
		}
	}
	
	/**
	 * Given a set of distinct integers, S, return all possible subsets.
	 * Note:
	 * Elements in a subset must be in non-descending order.
	 * The solution set must not contain duplicate subsets.
	 * For example,
	 * If S = [1,2,3], a solution is:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
	
	 * 
	 * Analysis:
	 * 
	 * 
	 * @param s
	 */
	public static void subsets(int[] s){
		if(s == null) return;
		List<int[]> res = new ArrayList<int[]>();
		for(int len = 1 ; len <= s.length ; len++){
			subsetOfCertainLength(s, len-1, 0, 0, new int[len], res);
		}
		
		System.out.println();
		for(int[] re : res){
			for(int i : re)
				System.out.print(i+", ");
			System.out.println();
		}
		System.out.println();
	}
	
	private static void subsetOfCertainLength(int[] s, int len, int th, int start, int[] path, List<int[]> res){
		if(th > len) {
			res.add(path);
			return;
		}
		
		for(int i = start ; i < s.length - len + th ; i++){
			path[th] = s[i];
			subsetOfCertainLength(s, len, th+1, i+1, Arrays.copyOf(path, path.length), res);
		}
		
	}
	/**
	 * Analysis:
	 * s = {1,2,3}
	 * 0. res = {[]}
	 * 1. res = {[],[1]}
	 * 2. res = {[],[1],[2],[1,2]}
	 * 3. res = {[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]}
	 * 
	 * From 2 to n, COPY the previous subsets, 
	 * add the current element, push back to the subsets list.
	 * 
	 * @param s
	 */
	public static void subsets1(int[] s){
		Arrays.sort(s);
		List<List<Integer>> res = new ArrayList<List<Integer>>();
		res.add(new ArrayList<Integer>());
		for(int i = 0 ; i < s.length ; i++){
			int j = res.size();
			while(j-- > 0){
				List<Integer> newlist = new ArrayList<Integer>();
				newlist.addAll(res.get(j));
				newlist.add(s[i]);
				res.add(newlist);
			}
		}
		
		System.out.println();
		for(List<Integer> re : res){
			for(int i : re)
				System.out.print(i+", ");
			System.out.println();
		}
		System.out.println();
	}
	
	/**
	 * Given a 2D board and a word, find if the word exists in the grid.
	 * The word can be constructed from letters of sequentially adjacent cell, 
	 * where "adjacent" cells are those horizontally or vertically neighboring. 
	 * The same letter cell may not be used more than once.
	 * For example,
	 * Given board =
[
  ["ABCE"],
  ["SFCS"],
  ["ADEE"]
]
		word = "ABCCED", -> returns true,
		word = "SEE", -> returns true,
		word = "ABCB", -> returns false.
		
	 * @param board
	 * @param word
	 */
	public static void wordSearch(char[][] board, char[] word){
		if(board == null || word == null) return;
		//find all start positions
		System.out.println();
		for(int i = 0 ; i < board.length ; i++)
			for(int j = 0 ; j < board[0].length ; j++){
				if(board[i][j] == word[0]){
					if(findPath(board, word, 0, i, j)) {
						System.out.println(true);
						return;
					}
				}
			}
		
		System.out.println(false);
	}
	
	private static boolean findPath(char[][] board, char[] word, int step, int x, int y){
		if(step >= word.length) 
			return true;
		if(board[x][y] == word[step]){
			board[x][y] = '*';
			int nextX = x, nextY = y;
			//up
			if(x == 0) nextX = board.length-1;
			else nextX = x - 1;
			
			if(!findPath(board, word, step+1, nextX, nextY)){
				//down
				if(x == board.length - 1) nextX = 0;
				else nextX = x + 1;
				
				if(!findPath(board, word, step+1, nextX, nextY)){
					//left
					if(y == 0) nextY = board[0].length - 1;
					else nextY = y - 1;
					nextX = x;
					
					if(!findPath(board, word, step+1, nextX, nextY)){
						//right
						if(y == board[0].length - 1) nextY = 0;
						else nextY = y + 1;
						nextX = x;
						if(!findPath(board, word, step+1, nextX, nextY)){
							board[x][y] = word[step];
							return false;
						}else return true;
					}else return true;
				}else return true;
			}else return true;
		}else return false;
	}
	
	
	/**
	 * Follow up for "Remove Duplicates":
	 * What if duplicates are allowed at most twice?
	 * For example,
	 * Given sorted array A = [1,1,1,2,2,3],
	 * Your function should return length = 5, and A is now [1,1,2,2,3].
	 * @param a
	 */
	public static void removeDuplicatesFromSortedArrayII(int[] a){
		if(a == null || a.length < 3) return;
		int count = 2;
		int ind = 1;
		int len = 0;
		
		while(ind < a.length - len){
			if(a[ind] == a[ind-1]) count--;
			else count = 2;
			if(count == 0){
				len++;
				for(int i = ind; i < a.length-1 ; i++)//move
					a[i] = a[i+1];
				continue;
			}
			ind++;
		}
		len = a.length - len;
		
		System.out.println();
		System.out.println("Length is: "+len);
		for(int i = 0 ; i < len ; i++)
			System.out.println(a[i]);
		
	}
	
	/**
	 * Follow up for "Search in Rotated Sorted Array":
	 * What if duplicates are allowed?
	 * Would this affect the run-time complexity? How and why?
	 * Write a function to determine if a given target is in the array.
	 * @param a
	 * @param target
	 */
	public static boolean searchInRotatedSortedArrayII(int[] a, int target){
		if(a == null) return false;
		int ind1 = 0, ind2 = a.length - 1;
		if(a[ind1] > target){
			for(; ind2 > 0 ; ind2++)
				if(a[ind2] == target) return true;
			return false;
		}
		
		if(a[ind2] < target){
			for(; ind1 < a.length ; ind1++)
				if(a[ind1] == target) return true;
			return false;
		}
		
		while(ind1 < ind2){
			if(a[ind1++] == target || a[ind2--] == target) return true;
		}
		
		return false;
	}
	
	/**
	 * Given a sorted linked list, 
	 * delete all duplicates such that each element appear only once.
	 * For example,
	 * Given 1->1->2, return 1->2.
	 * Given 1->1->2->3->3, return 1->2->3.
	 */
	public static void removeDuplicatesFromSortedList(ListNode head){
		if(head == null) return;
		ListNode pre = head, ind = head.next;
		while(ind != null){
			if(pre.val == ind.val){
				pre.next = ind.next;
				ind = null;
			}
			ind = pre.next;
		}
		
		System.out.println();
		while(head != null){
			System.out.print(head.val);
			head = head.next;
		}
		System.out.println();
	}
	
	/**
	 * Given a sorted linked list, delete all nodes that have duplicate numbers, 
	 * leaving only distinct numbers from the original list.
	 * For example,
	 * Given 1->2->3->3->4->4->5, return 1->2->5.
	 * Given 1->1->1->2->3, return 2->3.
	 */
	public static void removeDuplicatesFromSortedListII(ListNode head){
		if(head == null) return;
		ListNode pre = head, ind = head.next, prepre = null;
		while(ind != null){
			if(pre.val == ind.val){
				if(prepre != null){
					prepre.next = ind.next;
					pre = null; ind = null;
					pre = prepre.next;
					if(pre != null) ind = pre.next;
				}else{
					prepre = ind.next;
					if(pre == head) head = prepre;
					if(prepre != null){
						pre = prepre.next;
						if(pre != null)
							ind = pre.next;
						else ind = null;
					}else{
						ind = null;
						pre = null;
					}
				}
			}
		}
		
		System.out.println();
		while(head != null){
			System.out.print(head.val);
			head = head.next;
		}
		System.out.println();
	}
	
	/**
	 * Given n non-negative integers representing 
	 * the histogram's bar height where the width of each bar is 1, 
	 * find the area of largest rectangle in the histogram.
	 * Typical dynamic programming.
	 * 
	 * @param heights
	 */
	public static void largestRectangleInHistogram(int[] heights){
		if(heights == null) return;
		int len = heights.length;
		
		int[][] maxHeight = new int[len][len];
		
		for(int i = 0 ; i < len ; i++) maxHeight[i][i] = heights[i];
		
		for(int k = 1 ; k < len ; k++)
			for(int i = 0 ; i < len - k ; i++){
				maxHeight[i][i+k] = Math.max(maxHeight[i+1][i+k], maxHeight[i][i+k-1]);
				int minH = Integer.MAX_VALUE;
				for(int j = i ; j <= i+k ; j++)
					if(heights[j] < minH) minH = heights[j];
				maxHeight[i][i+k] = Math.max(maxHeight[i][i+k], minH * (k+1));
			}
		
		System.out.println();
		System.out.println("Area of largest rectangle is: "+maxHeight[0][len-1]);
	}
	
	/**
	 * ! Given a 2D binary matrix filled with 0's and 1's, 
	 * find the largest rectangle containing all ones and return its area.
	 * 
	 * A little bit like palindrome.
	 * @param matrix
	 */
	public static void maximalRectangle(int[][] matrix){
		if(matrix == null) return;
		int maxArea = Integer.MIN_VALUE;
		int x1 = -1, y1 = -1, x2 = -1, y2 = -1;
		
		for(int m = 0 ; m < matrix.length ; m++){
			for(int n = 0 ; n < matrix[0].length ; n++){
				if(matrix[m][n] == 1){//expanding
					boolean flagx = true, flagy = true;
					int dimx = 2;
					int dimy = 2;
					while(flagx || flagy){
						int mEnd = m+dimx-1;
						int nEnd = n+dimy-1;
						if(mEnd >= matrix.length || nEnd >= matrix[0].length) break;
						for(int i = m ; i < mEnd ; i++)
							for(int j = n ; j < nEnd ; j++)
								if(matrix[i][j] == 0){
									if(i <= mEnd) flagx = false;
									if(j <= nEnd) flagy = false;
									break;
								}
						if(flagx) dimx++;
						if(flagy) dimy++;
					}
					//renew
					int tempArea = dimx * dimy;
					if(tempArea > maxArea){
						maxArea = tempArea;
						x1 = m; y1 = n;
						x2 = m+dimx-1; y2 = n+dimy-1;
					}
				}
				
			}
		}
		
		System.out.println();
		System.out.println("Max Area is: "+ maxArea+" with coordinate: ["+x1+","+y1+","+x2+","+y2+"]");
		System.out.println();
		
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Color[] colors = new Color[6];
		Random ran = new Random();
		for(int i = 0 ; i < 6 ; i++){
			int k = ran.nextInt(3);
			if(k == 0) colors[i] = Color.RED;
			else if(k == 1) colors[i] = Color.WHITE;
			else colors[i] = Color.BLUE;
		}
		
		sortColors(colors);

		
		minimumWindowSubstring("ADOBECODEBANC", "ABC");
		
		combinations(9, 3);
		
		subsets(new int[]{1,2,3});
		subsets1(new int[]{1,2,3});
		
		char[][] board = new char[3][4];
		board[0] = "ABCE".toCharArray();
		board[1] = "SFCS".toCharArray();
		board[2] = "ADEE".toCharArray();
		
		wordSearch(board, "ABCB".toCharArray());
		
		removeDuplicatesFromSortedArrayII(new int[]{1,1,2,2,3,3,3,4,5,5});
		
		largestRectangleInHistogram(new int[]{2,1,5,6,2,3});
		
		int[][] matrix = new int[5][10];
		matrix[0] = new int[]{0,1,1,1,1,0,0,0,1};
		matrix[1] = new int[]{0,1,1,1,1,0,0,1,1};
		matrix[2] = new int[]{0,0,0,1,1,0,0,1,1};
		matrix[3] = new int[]{0,0,1,0,1,0,1,0,0};
		matrix[4] = new int[]{1,0,1,0,1,0,0,0,0};
		
		maximalRectangle(matrix);
	}

}

enum Color{
	RED("red",0), WHITE("white",1), BLUE("blue",2);
	private int index;
	private String name;
	private Color(String name, int index){
		this.index = index;
		this.name = name;
	}
	public int getIndex(){
		return this.index;
	}
	public String getName(){
		return this.name;
	}
}
